package leetcode101.ch4;
//LC 69
/**
 * 几个坑：
 * 1、0和1特殊处理
 * 2、中点的取法 如果用（l + r）/ 2 可能会造成无限循环
 * 3、乘法可能越界 mid * mid == x
 * 4、不能精确匹配时，返回的是左边界l而不是中点mid
 */


public class MySqrt {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int l = 1, r = x / 2, mid = -1;
        while (l < r) {
            System.out.println("l:"+ l + " r:"+r);
            mid = l + (r - l + 1) / 2;
            if (mid == x / mid) {
                return mid;
            }else if(mid  < x / mid) {
                l = mid;
            }else {
                r = mid - 1;
            }
        }
        return l;
    }

    public int mySqrt2(int x) {
        // 特殊值判断
        if (x <= 1) {
            return x;
        }
        int left = 1;
        int right = x / 2;
        // 在区间 [left..right] 查找目标元素
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 注意：这里为了避免乘法溢出，改用除法
            if (mid > x / mid) {
                // 下一轮搜索区间是 [left..mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索区间是 [mid..right]
                left = mid;
            }
        }
        return left;
    }


    public static void main(String[] args) {
        int sqrt = new MySqrt().mySqrt(2147395599);
        System.out.println(sqrt);
    }
}
